package written_examination_questions;

import javax.swing.tree.TreeNode;

public class Demo20251114 {
    /**
     * 将有序数组转换为二叉搜索树
     * @param nums
     * @return
     */
    // 根节点应是数组的中间元素（这样左右两边数量大致相等，保证平衡）
    // 左子树由左半部分构成（小于根）
    // 右子树由右半部分构成（大于根）
//    public TreeNode sortedArrayToBST(int[] nums) {
//        if (nums == null || nums.length == 0) {
//            return null;
//        }
//        return buildTree(nums, 0, nums.length - 1);
//    }

//    private TreeNode buildTree (int[] nums, int left, int right) {
//        if (left > right) return null;
//        // 选择中间元素作为根节点
//        int mid = left + (right - left) / 2;
//        TreeNode root = new TreeNode(nums[mid]);
//        // 递归构建左子树和右子树
//        root.left = buildTree(nums, left, mid - 1);
//        root.right = buildTree(nums, mid + 1, right);
//        return root;
//    }
    
    /**
     * 分割链表
     * @param head
     * @param x
     * @return
     */
//    public ListNode partition(ListNode head, int x) {
//        ListNode small = new ListNode(0);
//        ListNode large = new ListNode(0);
//        // 定义指针遍历链表
//        ListNode p = head, p1 = small, p2 = large;
//        while (p != null) {
//            ListNode next = p.next;
//            if (p.val < x) {
//                p1.next = p;
//                p1 = p1.next;
//            } else {
//                p2.next = p;
//                p2 = p2.next;
//            }
//            p.next = null; // 断开原来的链表，防止有环
//            p = next;
//        }
//        p1.next = large.next;
//        return small.next;
//    }
}
